package cn.edu.xjtu.work.findSecondMinimumValue;

import java.util.LinkedList;
import java.util.Queue;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/**
 * 671. 二叉树中第二小的节点
 * 
 * 给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
 * 
 * 更正式地说，root.val = min(root.left.val, root.right.val) 总成立。
 * 
 * 给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int min = Integer.MAX_VALUE;
        boolean flag = false;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                if (node.val != root.val) {
                    min = Math.min(min, node.val);
                    flag = true;
                }
                if (node.left != null) {
                    q.add(node.left);
                    q.add(node.right);
                }
            }
        }
        if (flag) {
            return min;
        }
        return -1;

    }
}
